One of the most common characteristics of transportation services is the serving of a series of pre-defined points, for example, train stops, bus stops, and goods delivery and pick-up points. Such a series of pre-defined points constitutes a service line with a specific origin and destination. Many transportation services have this characteristic, i.e. each vehicle serves a pre-determined set of sequential points, e.g. in both directions. For instance, a tram line serves a number of pre-defined tram stops between an origin terminal and a destination terminal and back.
Several studies have developed methods for allocating an optimal amount of resources (e.g., an optimal number of vehicles) to each service line of a broader transportation network (e.g., a network of bus lines in a city, a network of tram lines in a city, a network of logistic lines within a pick-up and delivery area) in a demand-responsive manner. Such studies include Gkiotsalitis et al. (K. Gkiotsalitis and O. Cats; Exact Optimization of Bus Frequency Settings Considering Demand and Trip Time Variations; 96th Transportation Research Board Annual Meeting, Paper No. 17-01871; January 2017) and Ibarra-Rojas et al. (O. Ibarra-Rojas, F. Delgado, R. Giesen, and J. Muñoz; Planning, operation, and control of bus transport systems: A literature review; Transportation Research Part B: Methodological, Vol. 77, 2015, pp. 38-75). The common objective of the vehicle/fleet allocation to lines is to simultaneously meet demand and limit operational costs given the constraint of resource limitations, e.g. a size of an available vehicle fleet. In those studies, the total number of available vehicles is distributed to different lines via a centralized optimization approach in order to satisfy demand at the line-level while limiting operational costs.
Additional previous work has focused on dividing the vehicle/fleet allocation problem into two stages, wherein all vehicles are pre-allocated at the line level during a first stage and minor adjustments are performed during a second stage by modifying routes for a small portion of the pre-allocated vehicles. Previous work has also utilized offline historical demand data between point couples to create additional fixed lines that cover only the specifically observed demand patterns. Such previous work includes, e.g., Verbas et al. (I. Verbas, C. Frei, H. Mahmassani, and R. Chan; Stretching resources: sensitivity of optimal bus frequency allocation to stop-level demand elasticities; Public Transport, Vol. 7, No. 1, 2015, pp. 1-20) and Verbas et al. (I. Verbas and H. Mahmassani, Optimal Allocation of Service Frequencies over Transit Network Routes and Time Periods: Formulation, Solution, and Implementation Using Bus Route Patterns; Transportation Research Record: Journal of the Transportation Research Board, 9 No. 2334, 2013, pp. 50-59).